{% extends "pages/base.html" %}
{% block title %}Home{% endblock %}
{% block content %}
Số phép so sánh tối thiểu cần sử dụng để tìm ra cả giá trị lớn nhất lẫn giá trị nhỏ nhất của một dãy gồm {N} phần tử là bao nhiêu? Ghi ra một số nguyên duy nhất là kết quả đáp án. ----------------------------------------------------------- Gợi ý phương pháp: Chia dãy thành hai nửa, tìm min và max mỗi nửa rồi so sánh chúng với nhau để tổng hợp kết quả. Xét mảng arr[lo..hi], mã giả để tìm min và max của mảng này như sau: Đáp án [100] Đáp án [100] O(1) [0] O(n) [0] O(nlogn) [0] O(logn) [0] Không đáp án nào đúng Trong các thuật toán dưới đây, thuật toán nào không phải là thuật toán chia
để trị? Đáp án [50] [0] Sắp xếp nhanh [0] Sắp xếp trộn [0] Tìm kiếm nhị phân Đáp án [50] Đáp án [100] O(logn) [0] O(n) [0] O(nlogn) [0] O(1) [0] O(log(logn)) [0] Không đáp án nào đúng Điều nào sau đây là đúng về độ phức tạp thuật toán là nghiệm của hệ thức truy hồi T(n)=2T(n/2) + logn với T (1) = 1? Đáp án [100] O(n) [0] O(nlogn) [0] O(logn) [0] O(n2) [0] Không đáp án nào đúng Cho mảng gồm các phần tử sau, 23, 32, 45, 69, 72, 73, 89, 97. Thuật toán sắp xếp nào dưới đây sử dụng ít phép so sánh nhất để sắp xếp mảng tăng dần? [0] Đáp án [100] [0] Merge sort [0] Quick sort sử dụng phần tử cuối cùng là phần tử pivot Thuật toán dưới đây có chức năng gì? Đáp án [100] [0] Tính tổng x+y [0] Tính phần dư của x chia cho y [0] Tìm bội số chung nhỏ nhất của x và y [0] Không đáp án nào đúng Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a. Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu? [0] 3 Đáp án [100] 4 [0] 5 [0] 6 [0] Đáp án khác Cấu trúc dữ liệu Deque cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau? [0] vào một đầu, ra đầu còn lại Đáp án [100] vào và ra được từ cả hai đầu [0] vào và ra duy nhất một đầu [0] không cách nào trong các cách ở đây [0] Đáp án khác Một thuật toán duyệt toàn bộ được gọi là hiệu quả: [0] khi có độ phức tạp tính toán là hàm mũ [0] khi có độ phức tạp tính toán là đa thức Đáp án [50] khi có độ phức tạp tính toán là hằng số [0] khi có độ phức tạp khấu trừ là tuyến tính Đáp án [50] khi có độ phức tạp khấu trừ là hằng số [0] khi có độ phức tạp khấu trừ là đa thức [0] Không mệnh đề nào trong các mệnh đề ở đây thoả mãn Trong các kỹ năng cơ bản dưới đây, kỹ năng nào cần rèn luyện trong khoá học? [0] Kỹ năng đọc đề [0] Kỹ năng phân loại bài toán [0] Kỹ năng kiểm thử chương trình
Câu 4143447
Algorithm: minmax(lo, hi)
if hi – lo ≤ 1 then
return (max(arr[lo], arr[hi]), min((arr[lo], arr[hi]))
else
(max1, min1):= minmax(lo, ⌊((lo + hi)/2)⌋)
(max2, min2):= minmax(⌊((lo + hi)/2) + 1)⌋, hi)
return (max(max1, max2), min(min1, min2))
Câu 4143448
Câu 4143449
Câu 4143450
Câu 4143451
Câu 4143452
Câu 4143453
Câu 4143454
Câu 4143455
Câu 4143456
Câu 4143457
[0] Kỹ năng phân tích thuật toán
Đáp án [100] Tất cả các kỹ năng ở đây
Giả sử độ phức tạp tính toán của giải thuật chia để trị khi giải một bài toán kích thước n có công thức truy hồi như sau:
$$ T(n) = 9 T(n/3) + n^2 $$
Dùng định lý thợ (master theorem), hãy xác định độ phức tạp tính toán của giải thuật trong trường hợp trên.
Đáp án [100]
\(\Theta(n^2logn) \)
[0]
\(\Theta(nlogn) \)
[0]
\(\Theta(n^2) \)
[0]
\(\Theta(nlog^2n) \)
[0] Đáp án khác
Trong các mục tiêu dưới đây, đâu là mục tiêu chính của môn học Thuật toán ứng dụng? (Có thể trả lời nhiều đáp án)
Đáp án [25]
Tăng cường khả năng mô hình hoá bài toán thực tế
Đáp án [25]
Tăng cường kỹ năng đề xuất Cấu trúc dữ liệu và Thuật toán cho các bài toán thực tế
Đáp án [25]
Tăng cường kỹ năng chuyển hoá thiết kế Cấu trúc dữ liệu và Thuật toán sang
chương trình có thể chạy được và đúng
Đáp án [25]
Tăng cường kỹ năng lập trình ngôn ngữ
[0]
Tăng cường kỹ năng phân tích, thiết kế các hệ thống thông tin lớn
Giả sử cho trước hàm sau:
int partition (int a[], int n);
Hàm này lấy phần tử đầu tiên của mảng a[] làm phần tử chốt, sau đó sắp xếp các phần tử nhỏ hơn hoặc bằng phần từ chốt về phần bên trái của mảng, và tất cả phần tử lớn hơn phần tử chốt về phần bên phải của mảng. Ngoài ra, hàm cũng di chuyển phần tử chốt về vị trí cuối cùng của phần bên trái. Hàm trả về số lượng phần tử của phần bên trái.
Đoạn chương trình C bị khuyết sau sử dụng hàm partition function để tìm phần tử nhỏ thứ k trong mảng a[] kích thước n (giả định k ≤ n). Hãy lựa chọn phần danh sách tham số đúng trong các phương án dưới đây để điền vào chỗ trống.
int kth_smallest (int a[], int n, int k) {
int left_end = partition (a, n);
if (left_end+1==k){
return a [left_end];
}
if (left_end+1 > k) {
return kth_smallest (____________________);
}
else {
return kth_smallest (____________________);
}
}Đáp án [100]
(a, left_end, k) và (a+left_end+1, n–left_end–1, k–left_end–1)
[0]
(a, left_end, k) và (a, n–left_end–1, k–left_end–1)
[0]
(a, left_end+1, N–left_end–1, K–left_end–1) và (a, left_end, k)
[0]
(a, n–left_end–1, k–left_end–1) và (a, left_end, k)
[0] Đáp án khác
Thuật toán chia để trị thường được lập trình theo phương pháp nào sau đây?
Đáp án [100]
Đệ quy
[0]
Dùng các vòng lặp
[0]
Quay lui
[0]
Dùng cú pháp lambda
[0] Đáp án khác
Trong những nhận định dưới đây về thuật toán chia để trị và quy hoạch động, nhận định nào đúng? (có thể chọn nhiều đáp án)
Đáp án [33.33333] Chia để trị thường được cài đặt bằng kỹ thuật đệ quy
Đáp án [33.33333] Quy hoạch động có thể được cài đặt bằng vòng lặp
[0] Trong quá trình giải bài toán, cả chia để trị và quy hoạch động đều cho độ phức tạp thuật toán trong thời gian đa thức
Đáp án [33.33333] Chia để trị chia bài toán lớn thành các bài toán con độc lập, trong khi đó quy hoạch động thì chia bài toán lớn thành các bài toán con gối nhau
Đại dịch COVID19 diễn ra phức tạp trên toàn thế giới. Việt Nam cũng không phải là ngoại lệ. Rất nhiều người đã bị chết vì dịch bệnh. Công ty phân tích dữ liệu XTEC muốn thống kê số lượng người chết theo các độ tuổi: nhỏ hơn 15, từ 15 tới 20, từ 20 tới 40, từ 40 tới 60 và trên 60. Yêu cầu, cho trước một danh sách người chết vì dịch bệnh và độ tuổi của những người này, hãy đưa ra số lượng người chết theo các độ tuổi trên.
Bài toán này thuộc dạng bài nào trong các dạng bài sau:
Đáp án [100] Adhoc
[0] Chia để trị
[0] Quy hoạch động
[0] Thuật toán đặc thù
[0] Thuật toán trên đồ thị
[0] Đáp án khác
Để giải nhanh và chính xác phương trình x3 + 2021x + 2 = 0 với -1000 ≤x ≤ 1000 với sai số chấp nhận được 10-6, chúng ta sử dụng phương pháp giải nào dưới đây?
[0] Duyệt toàn bộ
Đáp án [100] Chia để trị
[0] Quy hoạch động
[0] Thuật toán đặc thù
[0] Thuật toán trên đồ thị
[0] Đáp án khác
Phương pháp Qui hoạch động trên Bitmask giải bài toán người du lịch cho lời giải thế nào?
[0] Lời giải chấp nhận được (không đảm bảo tính tối ưu)
Đáp án [100] Lời giải tối ưu
[0] Đáp án khác
Cấu trúc dữ liệu Queue cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?
Đáp án [100] vào một đầu, ra đầu còn lại
[0] vào và ra được từ cả hai đầu
[0] vào và ra duy nhất một đầu
[0] không cách nào trong các cách ở đây
[0] đáp án khác
Trong một phiên bản giải thuật quicksort, người ta dùng một giải thuật \(O(n)\) để tìm phần tử nhỏ thứ \(n/5\) của dãy, và dùng phần tử này làm phần tử chốt. Hỏi độ phức tạp của giải thuật quicksort này trong trường hợp tồi nhất là bao nhiêu?
Đáp án [100]
\(O(nlogn)\)
[0]
\(O(n^5logn)\)
[0]
\(O(nlog^5n)\)
[0]
\(O(n^2)\)
[0] Đáp án khác
Cấu trúc dữ liệu Stack cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?
[0] vào một đầu, ra đầu còn lại
[0] vào và ra được từ cả hai đầu
Đáp án [100] vào và ra duy nhất một đầu
[0] không cách nào trong các cách ở đây
[0] đáp án khác
Nếu công thức truy hồi độ phức tạp tính toán của phương pháp tìm kiếm nhị phân (binary search) được biểu diễn dưới dạng \(T(n)=aT(n/b)+O(n^d)\) thì giá trị \(a+b+d\) là bao nhiêu? Ghi ra một số nguyên duy nhất là kết quả đáp án.
Đáp án [100]
3Biết rằng hàm số f(x) = x19 - x2 - x + 1 có một nghiệm nằm trong khoảng [0, 1], bạn được yêu cầu lập trình để tìm và điền nghiệm trên với sai số 10-6 vào ô trống.
Đáp án [100]
0.618082Cho dãy số nguyên [-9, 17, -16, -50, 19, -26, 28, 8, 12, 14, -45, -5, 31, -23, 11, 41, 45, -8, -23, -14], hãy tìm một đoạn con các phần tử liên tiếp trong dãy sao cho tổng mũ 3 của các phần tử trong đoạn con là lớn nhất và điền giá trị tổng này vào ô trống
Đáp án [100]
179001Xét đa thức p(x) = a0 + a1*x + a2*x2 + a3*x3, trong đó ai! = 0, với mọi i. Số phép nhân tối thiểu cần thiết để tính giá trị của p(x) với đầu vào x bất kỳ?
Đáp án [100] 3
[0] 4
[0] 6
[0] 9
[0] 12
[0] Đáp án khác
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án [100]
4
[0]
5
[0]
8
[0]
10
[0] Đáp án khác
Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.
Cho dãy số 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2 . Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?
[0]
7
[0]
14
[0]
20
Đáp án [100]
18
[0] Đáp án khác
Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.
Cho dãy số 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?
[0]
7
[0]
17
Đáp án [100]
21
[0]
27
[0] Đáp án khác
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 2, 5, 8, 6, 3, 4, 10, 14, 8. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
30
Đáp án [100]
31
[0]
32
[0]
33
[0]
34
[0] Đáp án khác
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 6, 4, 9, 2, 5, 9, 10, 14, 6. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
36
[0]
37
Đáp án [100]
38
[0]
40
[0]
42
[0] Đáp án khác
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. 9 phần tử 1,2…, 9 có trọng số tương ứng là 2, 6, 8, 1, 7, 4, 10, 4, 5. Hãy chọn ra tập con S các phần tử i[1] < i[2] < … < i[k] từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử i[j] và i[j+1] lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= i[j+1] – i[j] <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con lớn nhất). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
30
Đáp án [100]
32
[0]
34
[0]
35
[0] Đáp án khác
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
S.PUSH(i);
}
for i = 1 to 4 do {
x = S.POP();
}
x = S.POP();
print(x);
Đáp án [100] 5
[0] 2
[0] 9
[0] 4
[0] Đáp án khác
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
S.PUSH(i);
}
for i = 1 to 3 do{
x = S.POP();
}
x = S.POP();
print(x);
[0] 5
Đáp án [100] 7
[0] 6
[0] 4
[0] Đáp án khác
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 5 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
[0] 4
Đáp án [100] 3
[0] 2
[0] 5
[0] Đáp án khác
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 7 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
Đáp án [100] 5
[0] 3
[0] 4
[0] 6
[0] Đáp án khác
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0] 1
[0] 4
[0] 6
Đáp án [100] 5
[0] Đáp án khác
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 3 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0] 1
[0] 4
[0] 6
Đáp án [100] 7
[0] Đáp án khác
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 2 to 10 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0] 1
Đáp án [100] 5
[0] 2
[0] 7
[0] Đáp án khác
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0] 4
[0] 5
[0] 3
Đáp án [100] 7
[0] Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
Đáp án [100] 137
[0] 100
[0] 37
[0] 52
[0] Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0] 37
[0] 103
Đáp án [100] 11
[0] 42
[0] Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0] 30
Đáp án [100] 3
[0] 6
[0] 8
[0] Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0] 20
Đáp án [100] 4
[0] 5
[0] 9
[0] Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0] 10
[0] 4
[0] 6
Đáp án [100] 7
[0] Đáp án khác
Phát biểu nào sau đây không đúng
Đáp án [100] Các phần tử của danh sách liên kết luôn được cấp phát kế tiếp nhau trong bộ nhớ
[0] Các phần tử của danh sách liên kết không nhất thiết được cấp phát kế tiếp nhau trong bộ nhớ
[0] Không đáp án nào đúng
Phát biểu ”Ta truy nhập đến các phần tử của danh sách liên kết thông qua chỉ số” là đúng hay sai?
[0] Đúng
Đáp án [100] Sai
Phát biểu ”Thao tác tìm kiếm một phần tử trên danh sách liên kết có độ phức tạp trong tình huống tồi nhất là O(n) với n là số phần tử của danh sách liên kết” là đúng hay sai?
Đáp án [100] Đúng
[0] Sai
Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?
Đáp án [100] Đúng
[0] Sai
Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}
[0] Sắp xếp chèn
Đáp án [100] Sắp xếp lựa chọn
[0] Sắp xếp nổi bọt
[0] Sắp xếp vun đống
[0] Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
i = 1;
While s <= n {
s = s * 2;
i++;
}
}
Đáp án [100] \(O(logn)\)
[0] \(O(n)\)
[0] \(O(nlogn)\)
[0] Đáp án khác
Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )
f(n){
k = 1;
for i = 1 to n do{
While k <= n and a[k] < a[i] do{
k = k + 1;
}
}
}
[0] \(O(nlogn)\)
Đáp án [100] \(O(n)\)
[0] \(O(n^2)\)
[0] Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
If (n <= 1 ) return 0;
If n mod 2 = 0 {
Return 4*f(n/2) + 3n - 2;
}else{
Return 2*f(n/2) + 2n + 5;
}
}
[0] \(O(log(logn))\)
[0] \(O(n)\)
[0] \(O(n^\frac {1}{2})\)
Đáp án [100] \(O(logn)\)
[0] Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
a = 2;
i = 1;
While s <= n {
s = s * a;
a = a*a;
i = i + 1;
}
}
Đáp án [100] \(O(log(logn))\)
[0] \(O(n)\)
[0] \(O(n^\frac {1}{2})\)
[0] \(O(nlogn)\)
[0] Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = 2*a;
i++;
}
}
Đáp án [100] \(O(logn)\)
[0] \(O(n)\)
[0] \(O(n^\frac {1}{2})\)
[0] \(O(nlogn)\)
[0] Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = a + 1;
i = i + 1;
}
}
[0] \(O(logn)\)
[0] \(O(n)\)
Đáp án [100] \(O(n^\frac {1}{2})\)
[0] \(O(nlogn)\)
[0] Đáp án khác
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 2 x 4 x 2. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
9
[0]
8
Đáp án [100]
12
[0]
13
[0]
10
[0]
11
[0] Đáp án khác
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 4 x 4 x 3. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
10
[0]
9
Đáp án [100]
11
[0]
13
[0]
12
[0]
14
[0] Đáp án khác
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 8 và 3 x 3 x 5. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
12
[0]
13
Đáp án [100]
14
[0]
15
[0]
16
[0] Đáp án khác
Có bao nhiêu cách chia 20 cái kẹo cho 9 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
75582Có bao nhiêu cách chia 21 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
77520Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
31824Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
50388Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
27132Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
796510Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
195195Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án [100]
606320Phát biểu nào sau đây về quy lui (backtracking) là đúng?
[0]
Bài toán sinh tất cả các xâu nhị phân có độ dài cho trước không thể giải được bằng thuật toán quay lui
Đáp án [100]
Thuật toán quay lui có thể tìm ra giải pháp tối ưu cho bài toán tối ưu hóa tổ hợp
[0]
Thuật toán quay lui luôn có độ phức tạp thời gian tính toán đa thức
[0]
Thuật toán quay lui không thể tìm thấy bất kỳ lời giải tối ưu nào cho một bài toán tối ưu hóa tổ hợp
[0]
Đáp án khác
Cho đồ thị vô hướng G = (V, E), với V là tập đỉnh và E là tập cạnh. Ký hiệu, A[x] là tập các đỉnh kề với đỉnh x, với mọi x thuộc V.
Cho một hàm (được miêu tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào:
process(s, t){
Init an empty queue Q;
for x in V do
d[x] = -1;
Q.push(s);// push an element into the queue Q
d[s] = 0;
while Q not empty do{
u = Q.pop();// pop an element out of the queue Q
for v in A(u) do{
if d[v] = -1 then{
Q.push(v);
d[v] = d[u] + 1;
}
}
}
return d[t];
}
Phát biểu nào dưới đây là đúng?
Đáp án [100]
Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G
[0]
Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G
[0]
Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G
[0]
Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G
[0]
Đáp án khác
Cho đoạn chương trình dưới đây (miêu tả bằng mã giả), trong đó mảng a (các phần tử được đánh chỉ số từ 1 tới n), các biến toàn cục (global variables) n, m, T, cnt (a, n, m là tham số đầu vào)
solve(k){
for v = 0 to 1 do{
T = T + v*a[i];
if k = n then{
if T = m then
cnt = cnt + 1;
}else
solve(k+1);
}
}
main{
T = 0;
cnt = 0;
solve(1);
print(cnt);
}
Phát biểu nào dưới đây là đúng?
[0]
Chương trình tính số cách chọn các phần tử sao cho tổng các phần tử được chọn bằng m
[0]
Chương trình kiểm tra xem tổng các phần tử của a có bằng m không?
[0]
Chương trình tính số lần giá trị m xuất hiện trong mảng a
Đáp án [100]
Đáp án khác
Cho đồ thị vô hướng G = (V, E), trong đó V là tập đỉnh và E là tập cạnh. Ký hiệu A[x] là tập các đỉnh kề với đỉnh x (với mọi x thuộc V).
Cho hàm (được mô tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào.
process(s, t){
Init an empty queue Q;
for x in V do
d[x] = -1;
Q.push(s);// push an element into the queue Q
d[s] = 0;
while Q not empty do{
u = Q.pop();// pop an element out of the queue Q
print(u);
for v in A(u) do{
Q.push(v);
d[v] = d[u] + 1;
}
}
return d[t];
}
Phát biểu nào sau đây là đúng?
Đáp án [100]
Đáp án khác
[0]
Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều rộng
[0]
Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều sâu
[0]
Chương trình kết thúc và trả về độ dài (số cạnh) của đường đi ngắn nhất từ s tới t trên G
Cho một cây T = (V, E), trong đó V = {1,2,3,4,5,6,7,8,9,10,11,12,13} là tập các đỉnh và E = {(1,2), (1,12), (1,13), (2,3), (2,4), (3,7), (3,8), (3,9), (4,5), (4,6), (5,10), (5,11)} là tập các cạnh. Các đỉnh 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 lần lượt có trọng số 8, 6, 9, 1, 9, 2, 10, 2, 4, 3, 2, 5, 7. Tìm một tập con S các đỉnh trong V có tổng các trọng số lớn nhất sao cho 2 đỉnh bất kỳ trong S không kề nhau trên T. Tổng các trọng số các đỉnh trong S bằng bao nhiêu?
Đáp án [100]
37
[0]
35
[0]
38
[0]
39
[0]
43
[0]
45
[0]
46
[0]
Đáp án khác
Cho đoạn chương trình được miêu tả bởi một đoạn mã giả dưới đây, trong đó hàm P nhận một mảng a, n, W, T, k như tham số (thành phần của mảng a được đánh chỉ số từ 1 tới n) và cnt là một biến toàn cục.
P(a, n, W, T, k){
for v = 0 to 1 do {
if (k = n) then{
if (T + v*a[k] = W) then cnt = cnt + 1;
}else
P(a, n, W, T + v*a[k], k+1);
}
}
Main { // main function
a = {2,3,6,7,4,5}; // array indexed from 1 to 6
cnt = 0;
P(a, 6, 12, 0, 1);
print(cnt); // print the value cnt to the screen
}
Giá trị của cnt được in ra màn hình trong hàm Main là bao nhiêu?Đáp án [100]
4
[0]
2
[0]
3
[0]
5
[0]
6
[0]
8
[0]
9
[0]
Đáp án khác
Mỗi phần tử của một Min-Heap (được biểu diễn bởi một cây đầy đủ) có hai trường (id, k), trong đó id là định danh và k là khóa của phần tử. Min-Heap có các hàm (operations) sau:
Hiện hiện một chuỗi các thao tác sau trên Min-Heap:
Phát biểu nào dưới đây là đúng?
Đáp án [100]
Phần tử có định danh 4 là con phải của phần tử có định danh 8
[0]
Phần tử có định danh 4 là con trái của phần tử có định danh 8
[0]
Phần tử có định danh 2 là con phải của phần tử có định danh 8
[0]
Phần tử có định danh 2 là con trái của phần tử có định danh 8
[0]
Phần tử có định danh 1 là con phải của phần tử có định danh 7
[0]
Phần tử có định danh 1 là con trái của phần tử có định danh 7
[0]
Đáp án khác
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án [100]
3
[0]
4
[0]
6
[0]
9
[0]
Đáp án khác
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án [100]
4
[0]
5
[0]
8
[0]
10
[0]
Đáp án khác
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
[-50]
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
Đáp án [50]
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
Đáp án [50]
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
[-50]
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
[0]
Đáp án khác
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
Đáp án [25] \(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
Đáp án [25] \(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
Đáp án [25] \(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
Đáp án [25] \(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
[0]
Đáp án khác
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
Đáp án [50]
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=7\)
Đáp án [50]
\(S_1=5, S_2=2, S_3 =6, F_1=7, F_2=5, F_3=15\)
[-50]
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=6\)
[-50]
\(S_1=1, S_2=6, S_3 =5, F_1=5, F_2=10, F_3=7\)
[0]
Đáp án khác
Có \(n=9\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
Đáp án [50]
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Đáp án [50]
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =4, F_8=6, S_9 =6, F_9=8\)
[-50]
\(S_1=2, F_1=4, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
[-50]
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =6, F_4=8, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
[0]
Đáp án khác
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=19\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
Đáp án [50]
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=15\)
[-50]
\(C_1=16, C_2=8, C_3 =20, W_1=6, W_2=10, W_3=13\)
Đáp án [50]
\(C_1=16, C_2=8, C_3 =20, W_1=7, W_2=10, W_3=14\)
[-50]
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=14\)
[0]
Đáp án khác
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=11\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
[-50]
\(C_1=15, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
Đáp án [50]
\(C_1=16, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
Đáp án [50]
\(C_1=15, C_2=27, C_3 =13, W_1=5, W_2=10, W_3=6\)
[-50]
\(C_1=14, C_2=27, C_3 =12, W_1=5, W_2=10, W_3=6\)
[0]
Đáp án khác
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=4\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
[-50]
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=2\)
Đáp án [50]
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=3\)
[-50]
\(C_1=8, C_2=15, C_3=8, W_1=3, W_2=4, W_3=1\)
Đáp án [50]
\(C_1=8, C_2=10, C_3=8, W_1=2, W_2=4, W_3=3\)
[0]
Đáp án khác
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
50
[0]
60
Đáp án [100]
70
[0]
80
[0]
90
[0]
Đáp án khác
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
40
Đáp án [100]
50
[0]
60
[0]
70
[0]
80
[0]
Đáp án khác
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
10
[0]
20
Đáp án [100]
30
[0]
40
[0]
50
[0]
Đáp án khác
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 5, 2, 3, 7, 2, 3, 6, 3. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
[0]
26
[0]
27
Đáp án [100]
28
[0]
29
[0]
30
[0]
Đáp án khác
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 7, 1, 4, 2, 7, 6, 5, 3, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
Đáp án [100]
24
[0]
25
[0]
26
[0]
27
[0]
28
[0]
Đáp án khác
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 3, 1, 2, 6, 4, 3, 1, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
[0] 16
Đáp án [100] 18
[0] 19
[0] 23
[0]
Đáp án khác
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho nhân viên chăm sóc khách hàng này.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0] NP
Đáp án [100] NP-khó
[0] NP-đầy đủ
[0] P
[0]
Đáp án khác
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm. Hỏi có tồn tại một hành trình cho nhân viên chăm sóc khách hàng này với chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0] NP
[0] NP-khó
Đáp án [100] NP-đầy đủ
[0] P
[0]
Đáp án khác
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của một khách hàng để bảo trì sản phẩm của công ty và quay trở lại công ty mình sau khi xong việc. Có \(n\) vị trí trong thành phố 1,2,..,\(n\), địa điểm công ty là vị trí số 1 và địa điểm khách hàng là vị trí số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) vị trí này.
Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho nhân viên chăm sóc khách hàng này đến địa điểm khách hàng và quay trở về công ty sau khi xong việc. Hành trình có thể đi qua các vị trí trung gian.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0] NP
[0] NP-khó
[0] NP-đầy đủ
Đáp án [100] P
[0]
Đáp án khác
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho thương nhân đó.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0] NP
Đáp án [100] NP-khó
[0] NP-đầy đủ
[0] P
[0]
Đáp án khác
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hỏi có tồn tại một hành trình cho thương nhân này có chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0] NP
[0] NP-khó
Đáp án [100] NP-đầy đủ
[0] P
[0]
Đáp án khác
Một thương nhân ở thành phố A muốn tìm hiểu thị trường ở thành phố B. Có \(n\) thành phố 1,2,..,\(n\), thành phố A ở thành phố số 1 và thành phố B là thành phố số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) thành phố. Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho thương nhân này đi từ thành phố A đến thành phố B và quay trở về thành phố B sau khi xong việc. Hành trình có thể đi qua các thành phố trung gian trong số \(n\) thành phố.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0] NP
[0] NP-khó
[0] NP-đầy đủ
Đáp án [100] P
[0]
Đáp án khác
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 10, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
[0]
3
Đáp án [100]
4
[0]
6
[0]
Đáp án khác
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 7, b = 5, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 3 lít ở 1 trong 2 bình là bao nhiêu?
Đáp án [100]
4
[0]
5
[0]
6
[0]
Không có phương án nào thực hiện được
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 3, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
[0]
2
[0]
3
Đáp án [100]
4
[0]
5
[0]
Đáp án khác
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 2, b = 9, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 5 lít ở 1 trong 2 bình là bao nhiêu?
[0]
3
Đáp án [100]
4
[0]
5
[0]
Không có phương án thực hiện
Thuật toán Bellman-Ford tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây?
[-50]
Đồ thị tổng quát
Đáp án [25] Đồ thị không chứa chu trình âm
Đáp án [25] Đồ thị không có cạnh trọng số âm
Đáp án [25] Đồ thị có hướng không có chu trình DAG
Đáp án [25] Cây
[-50]
Đồ thị hai phía
[0]
Đáp án khác
Những mệnh đề nào sau đây là ĐÚNG?
Đáp án [50]
Nếu \(A \in NP\)-khó và \(A\prec B\), thì \(B \in NP\)-khó
[-50]
Nếu \(A \in NP\)-khó và \(B\prec A\), thì \(B \in NP\)-khó
[-50]
Nếu \(A \in P\) và \(A\prec B\), thì \(B \in P\)
Đáp án [50]
Nếu \(A \in P\) và \(B\prec A\), thì \(B \in P\)
[0]
Không đáp án nào đúng
Những phương pháp nào thường được sử dụng để đưa ra lời giải chấp nhận được mà không đảm bảo tính tối ưu trong thời gian đa thức cho bài toán thuộc lớp NP-khó?
Nhánh cận
Tham lam
Chia để trị
Qui hoạch động
Heuristic
Meta-heuristic
Học tăng cường
Thuật toán xấp xỉ
Tất cả các phương pháp liệt kê ở đây
[0]
Không đáp án nào đúng
Bài toán người du lịch với yêu cầu tối thiểu hoá chi phí hành trình của người du lịch thuộc lớp bài toán nào?
[0] NP
Đáp án [100] NP-khó
[0] NP-đầy đủ
[0] P
[0]
Đáp án khác
Những phương pháp nào có thể giải bài toán người du lịch cho lời giải chấp nhận được?
[0] Nhánh cận
[0] Tham lam
[0] Qui hoạch động
[0] Heuristic
[0] Meta-heuristic
[0] Học tăng cường
Đáp án [100] Tất cả các phương pháp trên
Những mối quan hệ nào sau đây là CHẮC CHẮN ĐÚNG?
Đáp án [25] \(P \subseteq NP\)
Đáp án [25] \(NPC \subseteq NP\)
\(P \subset NP\)
\(P \neq NP\)
\(P = NP\)
\(NPC = NP\)
\(NPC \subset NP\)
\(NPC \neq NP\)
Đáp án [25] \(NPC \subset NP\)-khó
Đáp án [25] \(NP\)-khó \(\cap NP = NPC\)
\(NP \subset NP\)-khó
\(P \neq NP\)-khó
[0]
Đáp án khác
Thuật toán Người thu ngân có cho lời giải tối ư với các đồng tiền mệnh giá 1xu, 5xu, 10xu, 25xu và 100xu không?
Đáp án [100]
trueCó
[0]
falseKhông
Cho đồ thị hai phía $G=(X\cup Y, E)$ với $|X|=${m}, $|Y|=${n}, $|E|=${k}, và lực lượng cặp ghép lớn nhất của $G$ là {s}. Hãy tính lực lượng tập độc lập lớn nhất của $G$.
Đáp án [100]
{n}+{m}-{s}+0*{k}Trong một phiên bản giải thuật quicksort dùng phần tử ở vị trí thứ n/5 làm phần tử chốt. Hỏi độ phức tạp của giải thuật quicksort này trong trường hợp tồi nhất là bao nhiêu?
[0]
\(O(nlogn)\)
[0]
\(O(n^5logn)\)
[0]
\(O(nlog^5n)\)
Đáp án [100]
\(O(n^2)\)
[0] Đáp án khác
Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a.
Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu?
[0]
3
Đáp án [100]
4
[0]
5
[0]
6
[0] Đáp án khác
Nhận định nào dưới đây là đúng khi so sánh biểu diễn đồ thị theo danh sách kề với biểu diễn đồ thị theo ma trận kề?
[0]
Biểu diễn theo danh sách kề sẽ tiết kiệm bộ nhớ hơn cho những ma trận thưa
[0]
DFS và BFS có thể thực hiện trong O(V+E) nếu sử dụng biểu diễn theo danh sách kề. Trong khi đó, nếu biểu diễn theo ma trận kề thì các thao tác này có độ phức tạp O(V2). Trong đó V, E lần lượt là số lượng đỉnh và cạnh của đồ thị.
[0]
Thêm một đỉnh vào đồ thị sẽ dễ dàng hơn khi biểu diễn theo danh sách kề so với biểu diễn đồ thị theo ma trận kề
Đáp án [100]
Tất cả các đáp án trên
Dãy bậc của một đơn đồ thị là dãy bậc của các đỉnh của đồ thị đó được sắp xếp giảm dần. Dãy nào sau đây không thể là dãy bậc của đồ thị nào đó?
I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2 III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1
Đáp án [100]
II và IV
[0]
I và II
[0]
III và IV
[0]
IV
[0]
Đáp án khác
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Đáp án [100]
gcĐáp án [100]
cgĐáp án [100]
c-gĐáp án [100]
g-cCác cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Đáp án [100]
dfĐáp án [100]
fdĐáp án [100]
d-fĐáp án [100]
f-dCác cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Đáp án [100]
cfĐáp án [100]
fcĐáp án [100]
c-fĐáp án [100]
f-cCác cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Đáp án [100]
gcĐáp án [100]
cgĐáp án [100]
c-gĐáp án [100]
g-cCác cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Đáp án [100]
dfĐáp án [100]
fdĐáp án [100]
d-fĐáp án [100]
f-dCác cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Đáp án [100]
cfĐáp án [100]
fcĐáp án [100]
c-fĐáp án [100]
f-cHãy ghép cặp thuật toán với bài toán phù hợp.
Thuật toán Dijkstra
Thuật toán Prim
Thuật toán Kruskal
Có thể xây dựng được bao nhiêu đồ thị vô hướng (không nhất thiết phải liên thông) với n đỉnh?
[0]
n(n-1)
[0]
[0]
2n
[0]
n!
Đáp án [100]
2(n(n-1)/2
[0]
Đáp án khác
Cho đồ thị vô hướng với trọng số \( G \) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \( G \).
Đáp án [100]
169Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Đáp án [100]
163Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Đáp án [100]
143Xét đồ thị có trọng số \(G\)như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Đáp án [100]
242Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Đáp án [100]
dhĐáp án [100]
hdĐáp án [100]
d-hĐáp án [100]
h-dCác cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Đáp án [100]
dfĐáp án [100]
fdĐáp án [100]
d-fĐáp án [100]
f-dCác cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Đáp án [100]
bfĐáp án [100]
fbĐáp án [100]
f-fĐáp án [100]
f-bCho đồ thị vô hướng trọng số trên cạnh như dưới đây
[0]
trueCó
Đáp án [100]
falseKhông
Cho đồ thị vô hướng với trọng số trên cạnh như dưới đây
[0]
trueCó
Đáp án [100]
falseKhông
Xét một đồ thị có hướng với n đỉnh và m cạnh sao cho tất cả các cạnh đều có trọng số các cạnh bằng nhau. Tìm độ phức tạp của thuật toán đã biết tốt nhất để tính cây khung nhỏ nhất của đồ thị?
Đáp án [100]
O(m+n)
[0]
O(m logn)
[0]
O(mn)
[0]
O(n logm)
[0]
Đáp án khác
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 14 đỉnh và 30 cạnh đều có bậc là 3 hoặc 5.
Do đó, số đỉnh có bậc là 3 của đồ thị G = {1:NUMERICAL:=5}
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 15 đỉnh và 25 cạnh đều có bậc là 2 hoặc 7.
Do đó, số đỉnh có bậc là 2 của đồ thị G = {1:NUMERICAL:=11}
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 54 cạnh đều có bậc là 3 hoặc 7.
Do đó, số đỉnh có bậc là 3 của đồ thị G = {1:NUMERICAL:=8}
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 52 cạnh đều có bậc là 4 hoặc 7.
Do đó, số đỉnh có bậc là 4 của đồ thị G = {1:NUMERICAL:=12}
Gọi G là một đồ thị đơn giản có 20 đỉnh và 8 thành phần liên thông. Nếu chúng ta xóa một đỉnh trong G, thì số thành phần trong G sẽ nằm trong khoảng nào dưới đây?
Đáp án [100]
7 - 19
[0]
8-20
[0]
8-19
[0]
7-20
[0]
Đáp án khác
Số lượng cạnh đối đa trong một chu trình trên một đồ thị vô hướng không chu trình gồm n đỉnh là bao nhiêu?
Đáp án [100]
n-1
[0]
n
[0]
n+1
[0]
2n-1
[0]
Đáp án khác
Thuật toán nào dưới đây hiệu quả nhất để tìm đường đi đơn ngắn nhất giữa 2 trong đồ thị tổng quát?
Đáp án [100] Đáp án khác
[0] Dijkstra
[0] Bellman-Ford
[0] Floyd-Warshall
[0] Prim
[0] Kruskal
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
[0]
C
Đáp án [100]
D
[0]
E
[0]
F
Cho đồ thị có hướng như trên hình vẽ:

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:[0]
E, D, F, C, B
[0]
E, D, C, B, F
[0]
E, C, B, F, D
[0]
E, C, B, D, F
Đáp án [100]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị có hướng như trên hình vẽ:

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:Đáp án [100]
E, D, B, F, C
[0]
E, D, C, B, F
[0]
E, C, B, F, D
[0]
E, C, B, D, F
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
[0]
C
[0]
D
[0]
E
Đáp án [100]
F
Cho đồ thị có hướng như trên hình vẽ:

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:[0]
C, E, B, D, F
[0]
C, E, F, D, B
[0]
C, F, E, D, B
[0]
C, F, E, B, D
Đáp án [100]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
Đáp án [100]
C
[0]
D
[0]
E
[0]
F
Cho đồ thị như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ đỉnh A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
[0]
C
[0]
D
Đáp án [100]
E
[0]
F
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Đáp án [100]
B
[0]
C
[0]
D
[0]
E
[0]
F
Để cài đặt thuật toán đường đi ngắn nhất Dijkstra trên đồ thị không có trọng số để nó chạy trong thời gian tuyến tính, cấu trúc dữ liệu sẽ được sử dụng là:
Đáp án [100]
Hàng đợi
[0]
Ngăn xếp
[0]
Đống (Heap)
[0]
B-Tree
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[6] bằng bao nhiêu?
Đáp án [100] 4
[0] 5
[0] 6
[0] 1
[0] 3
[0] Đáp án khác
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[11] bằng bao nhiêu?
[0] 4
[0] 5
Đáp án [100] 6
[0] 1
[0] 3
[0] Đáp án khác
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11), (10, 11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[10] bằng bao nhiêu?
Đáp án [100] 4
[0] 5
[0] 6
[0] 1
[0] 3
[0] Đáp án khác
Hãy xác định đâu là cây tìm kiếm theo chiều sâu xuất phát từ đỉnh 1 (kí hiệu là DFS(1)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Đáp án [100]

[0]

[0]

[0]

[0]

[0]
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 3 (kí hiệu là DFS(3)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Đáp án [100]

[0]

[0]

[0]

[0]

[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 2 (kí hiệu là DFS(2)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1, 2 ,3, 4, 5, 6, 7, 8.
[0]

Đáp án [100]


[0]

[0]

[0]

[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 4 (kí hiệu là DFS(4)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Đáp án [100]

[0]

[0]

[0]

[0]

[0]
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 4 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 4 đến đỉnh 7 là:
Đáp án [100]
4 --> 2 --> 5 --> 7
[0]
4 --> 5 --> 7
[0]
4 --> 2 --> 6 --> 7
[0]
4 --> 2 --> 8 --> 6 --> 7
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:
[0]
1 --> 4 --> 5 --> 7 --> 6
[0]
1 --> 2 --> 6
[0]
1 --> 2 --> 8 --> 6
[0]
1 --> 2 --> 5 --> 7 --> 6
Đáp án [100]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
[0]
1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:
Đáp án [100]
1 --> 2 --> 4 --> 5 --> 7 -->6
[0]
1 --> 2 --> 6
[0]
1 --> 2 --> 8 --> 6
[0]
1 --> 2 --> 5 --> 7 --> 6
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
[0]
1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:
[0]
3 --> 4 --> 5 --> 7 -->6
[0]
3 --> 1 --> 2 --> 6
[0]
3 --> 4 --> 2 --> 6
[0]
3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6
Đáp án [100]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
3 --> 4 --> 2 -->8 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:
Đáp án [100]
2 --> 1 --> 4 --> 5 --> 7
[0]
2 --> 8 --> 6 --> 7
[0]
2 --> 5 --> 7
[0]
2 --> 1 --> 8 --> 6 --> 7
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:
Đáp án [100]
3 --> 1 --> 2 --> 4 --> 5 --> 7 -->6
[0]
3 --> 1 --> 2 --> 6
[0]
3 --> 4 --> 2 --> 6
[0]
3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
[0]
3 --> 4 --> 2 -->8 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:
[0]
2 --> 4 --> 5 --> 7
[0]
2 --> 8 --> 6 --> 7
[0]
2 --> 5 --> 7
[0]
2 --> 1 --> 8 --> 6 --> 7
Đáp án [100]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 4 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
Đáp án [100]
1 --> 6 --> 4
[0]
1 --> 2 --> 5 --> 4
[0]
[0]
1 --> 3--> 2 --> 5 --> 4
[0]
1 --> 5 --> 4
[0] Đáp án khác
Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6, 7} và tập cạnh E ={(1,2), (1,3), (2,4), (2,5), (3,5), (4,6), (4,7), (5, 6), (5, 7), (6, 7)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 6 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
Đáp án [100]
1 --> 2 --> 4 --> 6
[0]
1 --> 3 --> 5 --> 7 --> 6
[0]
[0]
1 --> 3--> 5 --> 6
[0]
1 --> 5 --> 7 --> 6
[0] Đáp án khác
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {a, b, c, d, e, f, g} và tập cạnh E ={(a,b), (a,c), (b,d), (b,e), (c,e), (d,f), (d,g), (e, f), (e, g), (f, g)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phải từ đỉnh a (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh a đến đỉnh f trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
Đáp án [100]
a --> b --> d --> f
[0]
a --> c --> e --> g --> f
[0]
[0]
a --> c--> e --> f
[0]
a --> e --> g --> f
[0] Đáp án khác
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 6 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi độ dài đường đi (tính theo số lượng cạnh) từ đỉnh 6 đến đỉnh 3 là bao nhiêu?
Đáp án [100]
2
[0]
1
[0]
[0]
4
[0]
5
[0] Đáp án khác
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh s (kí hiệu: BFS(s)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
Đáp án [100]

[0]

[0]

[0]

[0] Đáp án khác
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh b (kí hiệu: BFS(b)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
Đáp án [100]

[0]

[0]

[0]

[0] Đáp án khác
Chúng ta có thể sử dụng các phương pháp tìm kiếm nào dưới đây để tìm tất cả các thành phần liên thông trong đồ thị vô hướng có trọng số G = (V,E, c)?
[0] Tìm kiếm theo chiều rộng (BFS)
[0] Tìm kiếm theo chiều sâu (DFS)
Đáp án [100] Tìm kiếm theo chiều rộng và chiều sâu
[0] Đáp án khác
Thuật toán nào dưới đây là phù hợp nhất để tìm thành phần liên thông mạnh trong một đồ thị có trọng số?
[0] Thuật toán tìm kiếm theo chiều rộng
Đáp án [100] Thuật toán tìm kiếm theo chiều sâu
[0] Thuật toán tìm kiếm theo chiều rộng và chiều sâu
[0] Đáp án khác
[0] Thuật toán dijkstra
Tìm đường đi ngắn nhất giữa 2 đỉnh trong đồ thị có hướng không trọng số G = (V, E) thì dùng thuật toán nào dưới đây phù hợp nhất?
Chú ý đường đi ngắn nhất giữa 2 đỉnh là đường đi qua ít cạnh nhất.
Đáp án [100] Tìm kiếm theo chiều rộng
[0] Tìm kiếm theo chiều sâu
[0] Thuật toán dijkstra
[0] Thuật toán Bellman-Ford
[0] Đáp án khác
Thuật toán hiệu quả nhất để tìm số lượng các thành phần liên thông trong một đồ thị vô hướng trên n đỉnh và m cạnh có độ phức tạp về thời gian là bao nhiêu?
[0]
θ(n)
[0]
θ(m)
Đáp án [100]
θ(m + n)
[0]
θ(mn)
[0]
Đáp án khác
Cấu trúc dữ liệu nào dưới đây phù hợp với duyệt độ thị theo chiều rộng?
[0]
Ngăn xếp
Đáp án [100]
Hàng đợi
[0]
Danh sách liên kết
[0]
Đáp án khác